home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1996 / MacHack 1996.toast / Presentations / Presentations ’96 / Sessions ’96 / Advanced Memory Mgmt / alloc_gla.c1.0.10 / alloc_gla.c < prev    next >
Encoding:
Text File  |  1996-06-17  |  23.5 KB  |  884 lines  |  [TEXT/KAHL]
  1. //
  2. //    alloc.c - Written by Glenn L. Austin
  3. //    Copyright © 1995 Symantec Corporation. All Rights Reserved.
  4. //
  5. //    Higher-performance, better heap management & validity checking.
  6. //    Also returns memory to the Macintosh if it isn't in use!!!
  7. //
  8. //    Revision history:
  9. //
  10. //    Release 1.0.10
  11. //    -------------
  12. //    * Added functionality for big blocks to automatically get returned to
  13. //      the application zone, regardless of the setting of gRestoreMemToHeap.
  14. //    * When allocating memory, I check to see if the existing zone(s) could
  15. //      satisfy the request before checking if the size is greater than the
  16. //      crossover size.
  17. //
  18. //    Release 1.0.9
  19. //    -------------
  20. //    * I missed yet one more assignment in 1.0.8 when the next block isn't
  21. //      a free block when freeing.
  22. //
  23. //    Release 1.0.8
  24. //    -------------
  25. //    * I missed an assignment in 1.0.7 when fixing the bug in free where, if the
  26. //      next block was the end of zone, it wasn't setting the size correctly for
  27. //      the newly freed block.
  28. //    * I now provide an AppleScript to update the ANSI libraries for both TPM and
  29. //      SPM to use alloc_gla.c instead of alloc.c.
  30. //
  31. //    Release 1.0.7
  32. //    -------------
  33. //    * There was a bug in free when the block that was being freed was the last
  34. //      block in a zone.  It wasn't getting combined with the previous block if
  35. //      the previous block was also a free block. (thanks DF)
  36. //
  37. //    Release 1.0.6
  38. //    -------------
  39. //    * Commented out the _UseAssert_ and _Debug_Alloc_GLA__ macros, since they
  40. //      shouldn't have been uncommented in the final version.
  41. //
  42. //    Release 1.0.5
  43. //    -------------
  44. //    * Bug fixed in alloc when the block is getting initialized.  It was allocating
  45. //      space for a block of the specified size, but was initializing for a maximum
  46. //      block size of sizeof(MemBlock) bytes smaller.
  47. //    * Bug fixed in calculating the 8 byte size (alignment). It was adding 8, which
  48. //      could allocate 8 bytes more than was necessary, if the requested size was
  49. //      already a multiple of 8.
  50. //
  51. //    Release 1.0.4
  52. //    -------------
  53. //    * Bug fixed in realloc when the block following this block was the end
  54. //      of the zone, which is a special "free" block.  Now special casing for
  55. //      end of zone.
  56. //    * Bug fixed in realloc when the block following this block was free, but
  57. //      wasn't large enough to satisfy the request for the resize.  Now mallocs
  58. //      a new block if this is the case.
  59. //    * Made sure all asserts were inside conditional compile flag.
  60. //    * Added CheckBlocks routine for testing allocations without I/O.
  61. //    * Sizes are now a multiple of 8, which means that addresses should also
  62. //      be a multiple of 8.  This will improve performance on PowerPC with
  63. //      doubles.
  64. //    
  65. //    Release 1.0.3
  66. //    -------------
  67. //    * Improved realloc performance when the next block is a free block since
  68. //      realloc will now manipulate the free block size rather than moving the
  69. //      current block if it is growing.
  70. //    * Fixed many annoying bugs in realloc when the new size would make the
  71. //      size of the following free block smaller than 2 bytes.
  72. //    
  73. //    Release 1.0.2
  74. //    -------------
  75. //    * Fixed problems with blocks larger than gMaxBlockSize.  They were still
  76. //      marked as free blocks, even though they were in use.
  77. //      
  78. //    Release 1.0.1
  79. //    -------------
  80. //    * Fixed problems with splitting a free block when the first free block
  81. //      would be close to the same size as the block being split.  The second
  82. //      block header would overwrite the beginne next block header.
  83. //    
  84. //    Release 1.0
  85. //    -----------
  86. //    * Initial release on Symantec C++ 8.0 CD
  87. //
  88.  
  89. //#define _UseAssert_
  90. //#define NDEBUG
  91. //#define __DUMPBLOCKS__    0
  92. //#define _Debug_Alloc_GLA__
  93.  
  94. #pragma options(assign_registers)
  95. #pragma options(honor_register)
  96. #pragma options(defer_adjust)
  97. #pragma options(redundant_loads)
  98.  
  99. Boolean DumpBlocks(void);
  100.  
  101. #ifdef _UseAssert_
  102. #include <assert.h>
  103. #ifdef NDEBUG
  104.     #define assertMsg(x)    ((void) 0)
  105. #else
  106.     #define assertMsg(x)    (__assert(#x, __FILE__, __LINE__))
  107. #endif
  108. #endif
  109. #ifndef __DUMPBLOCKS__
  110.  #ifdef __Debug_Alloc_GLA__
  111.   #define __DUMPBLOCKS__    1
  112.  #else
  113.   #define __DUMPBLOCKS__    0
  114.  #endif
  115. #endif
  116.  
  117. #if __DUMPBLOCKS__
  118. #include <stdio.h>
  119. #endif
  120. #include <stdlib.h>
  121.  
  122. #include <Memory.h>
  123. #include <OSUtils.h>
  124.  
  125. #ifndef kMaxBlockSize
  126. #define kMaxBlockSize    32768L
  127. #endif
  128.  
  129. #define kEndOfZone        (-1L)
  130. #define kZHPFlag        0x1204
  131. #define kBigZHPFlag        0x0313
  132.  
  133. #if USES68KINLINES
  134. #pragma parameter __D0 TGetPtrSize(__A0)
  135. extern pascal Size TGetPtrSize(Ptr thePtr) = 0xA021;
  136. #else
  137. #define TGetPtrSize(p)    GetPtrSize(p)
  138. #endif
  139.  
  140. #ifdef __Debug_Alloc_GLA__
  141. extern Boolean __MMPrimitiveAllocate;
  142. #else
  143. Boolean __MMPrimitiveAllocate = false;
  144. #endif
  145. unsigned long    gMaxBlockSize = kMaxBlockSize;
  146. Boolean            gRestoreMemToHeap = true;
  147.  
  148. void *prealloc(size_t size);
  149. void cleanupalloc(void);
  150.  
  151. #ifdef __Debug_Alloc_GLA__
  152. void _free(void *p);
  153. #else
  154. void free(void *p);
  155. #endif
  156.  
  157. #if defined(powerc) || defined (__powerc)
  158. #pragma options align=mac68k
  159. #endif
  160. typedef struct {
  161.     QElemPtr    qLink;
  162.     short        flag;
  163.     short        usageCounter;        // number of allocated blocks in this Block
  164.     long        nextFreeOfs;        // offset from qLink to first free block
  165.     long        bytesFree;            // bytes free in this block
  166. } ZoneHeader, *ZoneHdrPtr;
  167. #if defined(powerc) || defined(__powerc)
  168. #pragma options align=reset
  169. #endif
  170.  
  171. #if defined(powerc) || defined (__powerc)
  172. #pragma options align=mac68k
  173. #endif
  174. typedef struct {
  175.     long        blkSize;            // in free blocks, this is negative
  176.     long        zoneOfs;            // in free blocks, this is the offset to the next free block
  177.     //char        data[0];            // the address of the data in the block
  178. } MemBlock, *MemBlkPtr;
  179. #if defined(powerc) || defined(__powerc)
  180. #pragma options align=reset
  181. #endif
  182.  
  183. #if defined(powerc) || defined (__powerc)
  184. #pragma options align=mac68k
  185. #endif
  186. typedef struct {
  187.     short        qFlags;
  188.     QElemPtr    qHead;
  189.     QElemPtr    qTail;
  190.     long        bytesInBlocks;        // the number of bytes allocated from the Mac memory manager
  191.     long        bytesFree;            // the number of free bytes in Zones
  192. } ZoneQHdr;
  193. #if defined(powerc) || defined(__powerc)
  194. #pragma options align=reset
  195. #endif
  196.  
  197. static ZoneQHdr    gAllocQueue = {0, nil, nil, 0, 0};
  198.  
  199. static void *alloc(size_t size);    // allocates a new entry in the malloc heap & returns the block
  200.                                     // automatically makes space for the ZoneHeader and MemBlock
  201.                                     // initializes ZoneHeader, first MemBlock and trailing size
  202.  
  203. #ifdef __Debug_Alloc_GLA__
  204. void *_malloc(size_t size)
  205. #else
  206. void *malloc(size_t size)
  207. #endif
  208. {
  209.     void                    *p = nil;
  210.     register ZoneHdrPtr        zhp = nil;
  211.     register MemBlkPtr        mbp = nil;
  212.     MemBlkPtr                bmbp = nil;        // last mbp, so we can adjust zoneOfs
  213.     
  214. #ifdef _UseAssert_
  215.     assert((long) size >= 0);        // can't create a negative size
  216. #else
  217. #ifndef NDEBUG
  218.     if ((long) size < 0)
  219.         DebugStr("\p••• Error during malloc!  size < 0!");
  220. #endif
  221. #endif
  222.  
  223.     size = ((size + 7) & ~0x00000007);            // round up to even 8-byte sizes!!!
  224.     
  225.     if ((size > gAllocQueue.bytesFree) && (size > gMaxBlockSize))
  226.     {
  227.         zhp = (ZoneHdrPtr) alloc(size);
  228.         if (!zhp)
  229.             return(nil);
  230.         zhp->nextFreeOfs = sizeof(ZoneHeader) + sizeof(MemBlock) + size;
  231.         zhp->flag = kBigZHPFlag;
  232.         
  233.         mbp = (MemBlkPtr) ((Ptr) zhp + sizeof(ZoneHeader));
  234.         p = (void *) ((Ptr) mbp + sizeof(MemBlock));
  235.         mbp->blkSize = size + sizeof(MemBlock);
  236.         mbp->zoneOfs = (Ptr) zhp - (Ptr) mbp;                // zoneOfs must be negative
  237.     }
  238.     else
  239.     {
  240.         if (size > gAllocQueue.bytesFree)
  241.             zhp = nil;
  242.         else
  243.             zhp = (ZoneHdrPtr) gAllocQueue.qHead;
  244.         
  245.         while (zhp)
  246.         {
  247.             if (size - sizeof(MemBlock) <= zhp->bytesFree)
  248.             {
  249.                 mbp = (MemBlkPtr) ((Ptr) zhp + zhp->nextFreeOfs);
  250.                 bmbp = nil;
  251.                 while (mbp->blkSize != kEndOfZone)
  252.                 {
  253. #ifndef NDEBUG
  254.                     if ((mbp->blkSize >= 0) || (mbp->blkSize & 0x00000001) || (mbp->zoneOfs <= 0))
  255. #ifdef _UseAssert_
  256.                         assertMsg("••• Error in malloc heap! malloc heap is corrupt! •••");
  257. #else
  258.                         DebugStr("\p••• Error in malloc heap! malloc heap is corrupt! •••");
  259. #endif
  260. #endif
  261.                     if (size > -mbp->blkSize - sizeof(MemBlock))
  262.                     {
  263.                         bmbp = mbp;
  264.                         mbp = (MemBlkPtr) ((Ptr) mbp + mbp->zoneOfs);    // point to the next free block
  265.                     }
  266.                     else                                    // mbp points to the free block,
  267.                         break;                                // bmbp points to the last free block or nil
  268.                 }
  269.                 
  270.                 if (mbp->blkSize != kEndOfZone)
  271.                     break;                                    // zhp, mbp & bmbp are all set up now!
  272.             }
  273.             
  274.             zhp = (ZoneHdrPtr) zhp->qLink;
  275.         }
  276.         
  277.         if (!zhp)                                        // need a new free zone!
  278.         {
  279.             zhp = (ZoneHdrPtr) alloc(gMaxBlockSize);
  280.             if (!zhp)
  281.                 return(nil);
  282.             mbp = (MemBlkPtr) ((Ptr) zhp + sizeof(ZoneHeader));
  283.             bmbp = nil;
  284.         }
  285.         
  286.         // now, zhp points to a valid zone, mbp points to the free block in the zhp zone
  287.         // bmbp is nil if mpb is the first free block, otherwise it points to the last free
  288.         // block encountered during its search for free blocks
  289.         if (size <= -mbp->blkSize - sizeof(MemBlock))
  290.         {
  291.             MemBlkPtr    t = (MemBlkPtr) ((Ptr) mbp + sizeof(MemBlock) + size);
  292.             
  293.             // need to break the free block into two pieces?
  294.             if (size + (sizeof(MemBlock) << 1) < -mbp->blkSize)
  295.             {
  296.                 t->zoneOfs = mbp->zoneOfs - size - sizeof(MemBlock);    // points to the next free block!
  297.                 t->blkSize = size + mbp->blkSize + sizeof(MemBlock);    // since blkSize is negative, this works!
  298.                 gAllocQueue.bytesFree -= sizeof(MemBlock);                // needed more bytes from free space
  299.                 zhp->bytesFree -= sizeof(MemBlock);
  300.             }
  301.             else
  302.             {
  303.                 t = (MemBlkPtr) ((Ptr) mbp + mbp->zoneOfs);
  304.                 size = -mbp->blkSize - sizeof(MemBlock);
  305.             }
  306.             if (!bmbp)
  307.                 zhp->nextFreeOfs = (Ptr) t - (Ptr) zhp;        // point to the first free in zone
  308.             else
  309.                 bmbp->zoneOfs = (Ptr) t - (Ptr) bmbp;        // offset from last free to next free
  310.         }
  311.         mbp->blkSize = size + sizeof(MemBlock);
  312.         mbp->zoneOfs = (Ptr) zhp - (Ptr) mbp;                // zoneOfs must be negative
  313.         p = (void *) ((Ptr) mbp + sizeof(MemBlock));
  314.     }
  315.     
  316.     if (p)
  317.     {
  318.         gAllocQueue.bytesFree -= size;
  319.         
  320. #ifndef NDEBUG
  321.         if (!zhp)
  322. #ifdef _UseAssert_
  323.             assertMsg("••• Fatal error in malloc! Malloc heap corruption! •••");
  324. #else
  325.             DebugStr("\p••• Fatal error in malloc! Malloc heap corruption! •••");
  326. #endif
  327.         else
  328. #endif
  329.         {
  330.             ++zhp->usageCounter;
  331.             zhp->bytesFree -= size;
  332.         }
  333.     }
  334.     
  335.     return(p);
  336. }
  337.  
  338. #ifdef __Debug_Alloc_GLA__
  339. void *_calloc(size_t count, size_t size)
  340. #else
  341. void *calloc(size_t count, size_t size)
  342. #endif
  343. {
  344.     register size_t    siz = count * size;
  345.     register void    *p = malloc(siz);
  346.     register short    *q = (short *) p;
  347.     
  348.     if (!p)
  349.         return(nil);
  350.     
  351.     ++siz;
  352.     siz >>= 1;
  353.     while (siz--)
  354.         *q++ = 0;
  355.     
  356.     return(p);
  357. }
  358.  
  359. #ifdef __Debug_Alloc_GLA__
  360. void *_realloc(register void *oldptr, register size_t newsize)
  361. #else
  362. void *realloc(register void *oldptr, register size_t newsize)
  363. #endif
  364. {
  365.     register MemBlkPtr    mbp;
  366.     register MemBlkPtr    t;
  367.     ZoneHdrPtr            zhp;
  368.     void                *p;
  369.     register long        toCopy;
  370.     MemBlkPtr            newfr;
  371.     long                newSz = 0;
  372.     MemBlkPtr            fr;
  373.     long                freeChange = 0;
  374.     
  375. #ifdef _UseAssert_
  376.     assert((long) newsize >= 0);        // can't create a negative size
  377. #else
  378. #ifndef NDEBUG
  379.     if ((long) newsize < 0)
  380.         DebugStr("\p••• Error during realloc!  newsize < 0!");
  381. #endif
  382. #endif
  383.     
  384.     if (!oldptr)
  385.         return(malloc(newsize));        // realloc(NULL, newsize) == malloc(newsize)
  386.     else
  387.         mbp = (MemBlkPtr) ((Ptr) oldptr - sizeof(MemBlock));    // get memory block pointer
  388.  
  389.     if ((mbp->blkSize <= 0) ||            // invalid block pointer!  blkSize MUST be positive
  390.             (mbp->zoneOfs >= 0))        // and zoneOfs must be negative!
  391.         return(nil);
  392.     
  393.     newsize = ((newsize + 7) & ~0x00000007);    // size must be even!
  394.         
  395.     toCopy = mbp->blkSize - sizeof(MemBlock); // assume newsize > old size
  396.     if (toCopy == newsize)                // newsize == old size
  397.         return(oldptr);                    // return the old pointer!
  398.     
  399.     if (toCopy > newsize)                // if attempting to copy more than the free space...
  400.         toCopy = newsize;
  401.     
  402.     freeChange = mbp->blkSize - sizeof(MemBlock) - newsize;
  403.     
  404.     zhp = (ZoneHdrPtr) ((Ptr) mbp + mbp->zoneOfs);
  405.                                         // point to the zone header
  406.     t = (MemBlkPtr) ((Ptr) mbp + mbp->blkSize);
  407.                                         // point to the next block following this block
  408.     
  409.     // If the new block size is smaller than the old block, then shrink the block in
  410.     // size and create (or combine) a free block following this block
  411.     if (mbp->blkSize - sizeof(MemBlock) > newsize)
  412.     {
  413.     ResizeNextFree:
  414.         newfr = (MemBlkPtr) ((Ptr) mbp + newsize + sizeof(MemBlock));
  415.         fr = (MemBlkPtr) ((Ptr) zhp + zhp->nextFreeOfs);
  416.         
  417.         if (fr < mbp)
  418.         {
  419.             while (((Ptr) fr + fr->zoneOfs) < (Ptr) mbp)
  420.                 fr = (MemBlkPtr) ((Ptr) fr + fr->zoneOfs);    // point to next free block
  421.         }
  422.         else
  423.             fr = nil;
  424.  
  425.         p = oldptr;                        // block doesn't move
  426.         
  427.         if (t->blkSize == kEndOfZone)
  428.         {
  429.             if (freeChange < 0)            // new size > old size
  430.                 goto NewMallocBlock;
  431.             else                        // new size < old size
  432.             {
  433.                 if (fr)                        // there is a previous free block!
  434.                 {
  435.                     newfr->zoneOfs = fr->zoneOfs - (long) newfr + (long) fr;
  436.                     fr->zoneOfs = (Ptr) newfr - (Ptr) fr;
  437.                 }
  438.                 else                        // no previous free block!
  439.                 {
  440.                     newfr->zoneOfs = zhp->nextFreeOfs - (long) newfr + (long) zhp;
  441.                     zhp->nextFreeOfs = ((Ptr) newfr - (Ptr) zhp);
  442.                 }
  443.                 newfr->blkSize = (Ptr) newfr - (Ptr) t;
  444.                 mbp->blkSize = newsize + sizeof(MemBlock);
  445.             }
  446.         }
  447.         else if (t->blkSize < 0)                // next block is a free block!
  448.         {
  449.             newSz = t->blkSize - ((Ptr) t - (Ptr) newfr);
  450.             
  451.             if (newSz >= 0)
  452.                 goto NewMallocBlock;
  453.             else if (newSz >= -sizeof(MemBlock))
  454.             {
  455.                 freeChange += sizeof(MemBlock);
  456.                 mbp->blkSize -= t->blkSize;
  457.                 if (fr)                    // there is a previous free block!
  458.                     fr->zoneOfs += t->zoneOfs;
  459.                 else
  460.                     zhp->nextFreeOfs += t->zoneOfs;
  461.             }
  462.             else
  463.                 goto SetupNewFreeBlock;
  464.         }
  465.         // Is there enough room to create a new free block?
  466.         else if ((Ptr) t > ((Ptr) mbp + newsize + sizeof(MemBlock)))
  467.         {
  468.             newSz = ((Ptr) newfr - (Ptr) t);
  469.  
  470.             if (newSz < -sizeof(MemBlock))
  471.             {
  472.             SetupNewFreeBlock:
  473.                 if (fr)                        // there is a previous free block!
  474.                 {
  475.                     if (t->zoneOfs > 0)        // is the next block a free block?
  476.                         newfr->zoneOfs = t->zoneOfs + (Ptr) t - (Ptr) newfr;
  477.                     else
  478.                         newfr->zoneOfs = fr->zoneOfs - (long) newfr + (long) fr;
  479.                     fr->zoneOfs = ((Ptr) newfr - (Ptr) fr);
  480.                 }
  481.                 else                        // no previous free block!
  482.                 {
  483.                     if (t->zoneOfs > 0)
  484.                         newfr->zoneOfs = t->zoneOfs + ((Ptr) t - (Ptr) newfr);
  485.                     else
  486.                         newfr->zoneOfs = zhp->nextFreeOfs - (long) newfr + (long) zhp;
  487.                     zhp->nextFreeOfs = ((Ptr) newfr - (Ptr) zhp);
  488.                 }
  489.                 newfr->blkSize = newSz;
  490.                 mbp->blkSize = newsize + sizeof(MemBlock);
  491.             }
  492.             else
  493.                 freeChange = 0;
  494.         }
  495.     }
  496.     // Otherwise the new block size is larger than the old block, so create a new block
  497.     // and copy the contents of the old block to the new block, then dispose the old block.
  498.     else
  499.     {
  500.         if (t->blkSize < 0)            // next block is a free block!
  501.             goto ResizeNextFree;
  502.         else
  503.         {
  504.         NewMallocBlock:
  505. #ifdef __Debug_Alloc_GLA__
  506.             p = _malloc(newsize);
  507. #else
  508.             p = malloc(newsize);
  509. #endif
  510.             freeChange = 0;
  511.             if (!p)
  512.                 return(nil);
  513.             BlockMove(oldptr, p, toCopy);    // copy the contents of the old block to the new block
  514. #ifdef __Debug_Alloc_GLA__
  515.             _free(oldptr);
  516. #else
  517.             free(oldptr);
  518. #endif
  519.         }
  520.     }
  521.     
  522.     gAllocQueue.bytesFree += freeChange;
  523.     zhp->bytesFree += freeChange;
  524.     
  525.     return(p);
  526. }
  527.  
  528. #ifdef __Debug_Alloc_GLA__
  529. void _free(void *p)
  530. #else
  531. void free(void *p)
  532. #endif
  533. {
  534.     register MemBlkPtr        mbp;
  535.     register ZoneHdrPtr        zhp;
  536.     
  537.     if (!p)
  538.         return;
  539.     
  540.     mbp = (MemBlkPtr) ((Ptr) p - sizeof(MemBlock));
  541.     
  542. #ifndef NDEBUG
  543.     if ((mbp->blkSize & 0x00000001) || (mbp->zoneOfs >= 0))
  544.     {
  545. #ifdef _UseAssert_
  546.         assertMsg("••• Error during free in malloc heap! malloc heap is corrupt! •••");
  547. #else
  548.         DebugStr("\p••• Error during free in malloc heap! malloc heap is corrupt! •••");
  549.         return;
  550. #endif
  551.     }
  552. #endif
  553.     
  554. #ifndef NDEBUG
  555.     if (mbp->blkSize <= 0)                    // invalid or free block!
  556.     {
  557. #ifdef _UseAssert_
  558.         assertMsg("••• Error during free -- invalid or free block! •••");
  559. #else
  560.         DebugStr("\p••• Error during free -- invalid or free block! •••");
  561.         return;
  562. #endif
  563.     }
  564. #endif
  565.  
  566.     zhp = (ZoneHdrPtr) ((Ptr) mbp + mbp->zoneOfs);
  567.                                             // point to the zone header
  568.     
  569.     // now, we know that either someone was extremely clever, or someone was extremely stupid
  570.     // we'll verify that by checking zhp->flag
  571. #ifndef NDEBUG
  572.     if ((zhp->flag != kZHPFlag) && (zhp->flag != kBigZHPFlag))              // not a valid pointer!
  573.     {
  574. #ifdef _UseAssert_
  575.         assertMsg("••• Error during free -- bad magic! •••");
  576. #else
  577.         DebugStr("\p••• Error during free -- bad magic! •••");
  578.         return;
  579. #endif
  580.     }
  581. #endif
  582.     
  583.     gAllocQueue.bytesFree += mbp->blkSize - sizeof(MemBlock);    // adjust bytesFree
  584.     zhp->bytesFree += mbp->blkSize - sizeof(MemBlock);
  585.                                         
  586.     if (--zhp->usageCounter || !(gRestoreMemToHeap || (zhp->flag == kBigZHPFlag)))    // still have blocks allocated in this zone
  587.     {
  588.         MemBlkPtr    t = (MemBlkPtr) ((Ptr) mbp + mbp->blkSize);        // point to the next block
  589.         MemBlkPtr    q = (MemBlkPtr) ((Ptr) zhp + zhp->nextFreeOfs);    // point to the first free block
  590.         Boolean        blkCombined = false;
  591.         
  592. #ifndef NDEBUG
  593.         if ((t->blkSize ^ t->zoneOfs) >= 0)
  594.         {
  595.             ++zhp->usageCounter;
  596.             gAllocQueue.bytesFree -= mbp->blkSize - sizeof(MemBlock);    // adjust bytesFree
  597.             zhp->bytesFree -= mbp->blkSize - sizeof(MemBlock);
  598. #ifdef _UseAssert_
  599.             assertMsg("••• Error during free in malloc heap! End of pointer overwritten! •••");
  600. #else
  601.             DebugStr("\p••• Error during free in malloc heap! End of pointer overwritten! •••");
  602.             return;
  603. #endif
  604.         }
  605. #endif
  606.         if (q < mbp)
  607.         {
  608.             while (((Ptr) q + q->zoneOfs) < (Ptr) mbp)
  609.                 q = (MemBlkPtr) ((Ptr) q + q->zoneOfs);    // point to next free block
  610.         }
  611.         else
  612.             q = nil;
  613.         
  614.         // q now points to the previous block, which is a free block, or nil
  615.         
  616.         if (t->blkSize != kEndOfZone)    // not last block in Block
  617.         {
  618.             if (t->blkSize < 0)            // next block is already a free block...
  619.             {
  620.                 mbp->zoneOfs = t->zoneOfs + mbp->blkSize;    // point to next free block!
  621.                 mbp->blkSize = -(mbp->blkSize - t->blkSize);
  622.                                         // add the old free block to this block!
  623.                 gAllocQueue.bytesFree += sizeof(MemBlock);    // we got rid of one header
  624.                 zhp->bytesFree += sizeof(MemBlock);
  625.                 blkCombined = true;
  626.             }
  627.             else
  628.                 mbp->blkSize = -mbp->blkSize;
  629.         }
  630.         else
  631.             mbp->blkSize = -mbp->blkSize;
  632.         
  633.         if (q)                    // there was a prior free block!
  634.         {
  635.             if (!blkCombined)
  636.                 mbp->zoneOfs = q->zoneOfs - ((Ptr) mbp - (Ptr) q);
  637.             if ((((Ptr) q - q->blkSize) == (Ptr) mbp))
  638.             {
  639.                 q->zoneOfs = mbp->zoneOfs - q->blkSize;
  640.                 q->blkSize += mbp->blkSize;
  641.                 gAllocQueue.bytesFree += sizeof(MemBlock);    // we got rid of a header
  642.                 zhp->bytesFree += sizeof(MemBlock);
  643.             }
  644.             else
  645.                 q->zoneOfs = (Ptr) mbp - (Ptr) q;
  646.         }
  647.         else
  648.         {
  649.             if (!blkCombined)
  650.                 mbp->zoneOfs = zhp->nextFreeOfs - ((Ptr) mbp - (Ptr) zhp);
  651.             zhp->nextFreeOfs = (Ptr) mbp - (Ptr) zhp;
  652.         }
  653.     }
  654.     else
  655.     {
  656.         register long    pSize;
  657.         
  658.         __MMPrimitiveAllocate = true;
  659.         pSize = TGetPtrSize((Ptr) zhp);
  660.         gAllocQueue.bytesInBlocks -= pSize;
  661.         gAllocQueue.bytesFree -= zhp->bytesFree;
  662.         Dequeue((QElemPtr) zhp, (QHdrPtr) &gAllocQueue.qFlags);
  663.         DisposPtr((Ptr) zhp);
  664.         __MMPrimitiveAllocate = false;
  665.     }
  666. }
  667.  
  668. void *prealloc(size_t size)
  669. {
  670.     void                    *p = nil;
  671.     register ZoneHdrPtr    zhp = nil;
  672.     
  673.     size = ((size + 7) & ~0x00000007);            // round up to even sizes!!!
  674.     
  675.     if (size < gMaxBlockSize)
  676.         size = gMaxBlockSize;
  677.     
  678.     zhp = (ZoneHdrPtr) alloc(size);
  679.     if (zhp)
  680.         p = (void *) ((Ptr) zhp + sizeof(ZoneHeader) + sizeof(MemBlock));
  681.     
  682.     return(p);
  683. }
  684.  
  685. void cleanupalloc(void)
  686. {
  687.     register ZoneHdrPtr    zhp = (ZoneHdrPtr) gAllocQueue.qHead;
  688.     
  689.     while (zhp)
  690.     {
  691.         if (!zhp->usageCounter)
  692.         {
  693.             register long    pSize;
  694.             ZoneHdrPtr        next = (ZoneHdrPtr) zhp->qLink;
  695.             
  696.             __MMPrimitiveAllocate = true;
  697.             pSize = TGetPtrSize((Ptr) zhp);
  698.             gAllocQueue.bytesInBlocks -= pSize;
  699.             gAllocQueue.bytesFree -= zhp->bytesFree;
  700.             Dequeue((QElemPtr) zhp, (QHdrPtr) &gAllocQueue.qFlags);
  701.             DisposPtr((Ptr) zhp);
  702.             __MMPrimitiveAllocate = false;
  703.             
  704.             zhp = next;
  705.         }
  706.         else
  707.             zhp = (ZoneHdrPtr) zhp->qLink;
  708.     }
  709. }
  710.  
  711. static void *alloc(register size_t size)
  712. {
  713.     register long            blockSize = size + sizeof(ZoneHeader) +
  714.                                     (sizeof(MemBlock) << 1);
  715.     register ZoneHdrPtr    zhp;
  716.     register MemBlkPtr        mbp;
  717.     
  718.     __MMPrimitiveAllocate = true;
  719.     zhp = (ZoneHdrPtr) NewPtr(blockSize);
  720.     __MMPrimitiveAllocate = false;
  721.     
  722.     if (!zhp)
  723.         return(nil);
  724.     
  725.     zhp->qLink = nil;
  726.     zhp->flag = kZHPFlag;
  727.     zhp->usageCounter = 0;
  728.     zhp->nextFreeOfs = sizeof(ZoneHeader);
  729.     zhp->bytesFree = size;
  730.     mbp = (MemBlkPtr) ((Ptr) zhp + sizeof(ZoneHeader));
  731.     mbp->zoneOfs = size + sizeof(MemBlock);
  732.     mbp->blkSize = -mbp->zoneOfs;
  733.     mbp = (MemBlkPtr) ((Ptr) mbp + size + sizeof(MemBlock));
  734.     mbp->blkSize = kEndOfZone;
  735.     mbp->zoneOfs = -kEndOfZone;
  736.     
  737.     gAllocQueue.bytesInBlocks += size + sizeof(ZoneHeader) + sizeof(MemBlock) + sizeof(long);
  738.     gAllocQueue.bytesFree += size;
  739.     Enqueue((QElemPtr) zhp, (QHdrPtr) &gAllocQueue.qFlags);    // add the memory block to the queue
  740.     
  741.     return(zhp);
  742. }
  743.  
  744. enum { bFreeZoneOfsBad, bUsedZoneOfsBad, bEndOfZoneOverwritten,
  745.         bFreeOffsetIncorrect, bEndOfZoneFreeOverwritten,
  746.         
  747.         kFreeZoneOfsBad = (1 << bFreeZoneOfsBad),
  748.         kUsedZoneOfsBad = (1 << bUsedZoneOfsBad),
  749.         kEndOfZoneOverwritten = (1 << bEndOfZoneOverwritten),
  750.         kFreeOffsetIncorrect = (1 << bFreeOffsetIncorrect),
  751.         kEndOfZoneFreeOverwritten = (1 << bEndOfZoneFreeOverwritten)
  752. };
  753.  
  754. short CheckBlocks(void)
  755. {
  756.     register ZoneHdrPtr        zhp = (ZoneHdrPtr) gAllocQueue.qHead;
  757.     register MemBlkPtr        mhp;
  758.     register MemBlkPtr        mbp;
  759.     register short            blockErrors = 0;
  760.     
  761.     while (!blockErrors && zhp)
  762.     {
  763.         mhp = (MemBlkPtr) ((Ptr) zhp + sizeof(ZoneHeader));
  764.         
  765.         while (!blockErrors && (mhp->blkSize != kEndOfZone))
  766.         {
  767.             if (mhp->blkSize < 0)
  768.             {
  769.                 if (mhp->zoneOfs <= 0)
  770.                     blockErrors |= kFreeZoneOfsBad;
  771.                 mhp = (MemBlkPtr) ((Ptr) mhp - mhp->blkSize);
  772.             }
  773.             else
  774.             {
  775.                 if (mhp->zoneOfs >= 0)
  776.                     blockErrors |= kUsedZoneOfsBad;
  777.                 mhp = (MemBlkPtr) ((Ptr) mhp + mhp->blkSize);
  778.             }
  779.         }
  780.         if (mhp->zoneOfs != -kEndOfZone)
  781.             blockErrors |= kEndOfZoneOverwritten;
  782.         mhp = (MemBlkPtr) ((Ptr) zhp + zhp->nextFreeOfs);
  783.         mbp = nil;
  784.         
  785.         while (!blockErrors && (mhp->blkSize != kEndOfZone))
  786.         {
  787.             if (mhp->blkSize < 0)
  788.             {
  789.                 mbp = mhp;
  790.                 mhp = (MemBlkPtr) ((Ptr) mhp + mhp->zoneOfs);
  791.             }
  792.             else
  793.             {
  794.                 blockErrors |= kFreeOffsetIncorrect;
  795.                 break;
  796.             }
  797.         }
  798.         if (mhp->zoneOfs != -kEndOfZone)
  799.             blockErrors |= kEndOfZoneFreeOverwritten;
  800.         
  801.         zhp = (ZoneHdrPtr) zhp->qLink;
  802.     }
  803.     
  804.     return(blockErrors);
  805. }
  806.  
  807. #if __DUMPBLOCKS__
  808. Boolean DumpBlocks(void)
  809. {
  810.     register ZoneHdrPtr    zhp = (ZoneHdrPtr) gAllocQueue.qHead;
  811.     register MemBlkPtr        mhp;
  812.     register MemBlkPtr        mbp;
  813.     register Boolean        blocksOK = true;
  814.     
  815.     printf("\n\nDumpBlocks:\n");
  816.     while (zhp)
  817.     {
  818.         printf("Zone at %08lx:\n", (long) zhp);
  819.         printf("--qLink:  %08lx\n--flag:   %04x\n--usage:  %d\n--freeO:  %ld\n--FreeB:  %ld\n",
  820.                 zhp->qLink, zhp->flag, zhp->usageCounter, zhp->nextFreeOfs, zhp->bytesFree);
  821.         
  822.         mhp = (MemBlkPtr) ((Ptr) zhp + sizeof(ZoneHeader));
  823.         
  824.         while (mhp->blkSize != kEndOfZone)
  825.         {
  826.             if (mhp->blkSize < 0)
  827.             {
  828.                 printf("  free block:  size %ld\n", -mhp->blkSize);
  829.                 if (mhp->zoneOfs <= 0)
  830.                 {
  831.                     printf("••• Error ••• Offset (%ld) is incorrect!\n", mbp->zoneOfs);
  832.                     blocksOK = false;
  833.                 }
  834.                 mhp = (MemBlkPtr) ((Ptr) mhp - mhp->blkSize);
  835.             }
  836.             else
  837.             {
  838.                 printf("  used block:  size %ld\n", mhp->blkSize);
  839.                 if (mhp->zoneOfs >= 0)
  840.                 {
  841.                     printf("••• Error ••• Offset (%ld) is incorrect!\n", mbp->zoneOfs);
  842.                     blocksOK = false;
  843.                 }
  844.                 mhp = (MemBlkPtr) ((Ptr) mhp + mhp->blkSize);
  845.             }
  846.         }
  847.         printf("End of zone\n");
  848.         if (mhp->zoneOfs != -kEndOfZone)
  849.         {
  850.             printf("••• Error ••• End of zone has been overwritten!!!\n");
  851.             blocksOK = false;
  852.         }
  853.         mhp = (MemBlkPtr) ((Ptr) zhp + zhp->nextFreeOfs);
  854.         mbp = nil;
  855.         
  856.         while (mhp->blkSize != kEndOfZone)
  857.         {
  858.             if (mhp->blkSize < 0)
  859.             {
  860.                 printf("  free block:  size %ld\n", -mhp->blkSize);
  861.                 mbp = mhp;
  862.                 mhp = (MemBlkPtr) ((Ptr) mhp + mhp->zoneOfs);
  863.             }
  864.             else
  865.             {
  866.                 blocksOK = false;
  867.                 printf("••• Error ••• Offset (%ld) is incorrect!\n", mbp->zoneOfs);
  868.                 break;
  869.             }
  870.         }
  871.         printf("End of free blocks!\n");
  872.         if (mhp->zoneOfs != -kEndOfZone)
  873.         {
  874.             printf("••• Error ••• End of zone/free blocks has been overwritten!!!\n");
  875.             blocksOK = false;
  876.         }
  877.         
  878.         zhp = (ZoneHdrPtr) zhp->qLink;
  879.     }
  880.     
  881.     return(blocksOK);
  882. }
  883. #endif
  884.